using System.Collections.Generic;
using Kopernikus.Collections.Generic;
using Kopernikus.Parsing.GenericParsing;
using Kopernikus.Parsing.LR;
using Kopernikus.Parsing.Utility;

namespace Kopernikus.Parsing.Earley
{
    public class EarleyParser<T, S> : IEarleyParser<T, S> where T : IConvertToSymbol
    {
        private readonly EarleyDFA m_dfa;
        private readonly EarleyGoal m_goal;
        private readonly IGrammar m_grammar;
        private readonly int m_initialState;

        public EarleyParser(IGrammar grammar) : this(grammar, EarleyParserOptions.None)
        {
        }

        public EarleyParser(IGrammar grammar, EarleyParserOptions options)
        {
            m_grammar = new NNFGrammar(grammar);
            if ((options & EarleyParserOptions.Precompile) != 0)
            {
                m_dfa = new FullEarleyDFA(Grammar);
            }
            else
            {
                m_dfa = new LazyEarleyDFA(Grammar);
            }

            m_initialState = m_dfa.Build();

            m_goal = new EarleyGoal(Grammar, m_dfa, m_initialState);
        }

        #region IEarleyParser<T,S> Members

        public IGrammar Grammar
        {
            get { return m_grammar; }
        }

        public S Parse(IEarleyEvaluator<T, S> evaluator, IEnumerable<T> symbols)
        {
            EarleyChart<T, S> chart = new EarleyChart<T, S>(Grammar, m_dfa);

            Set<EarleyItem> startSet = new Set<EarleyItem>();
            startSet.Add(EarleyItem.Create(m_initialState, 0));
            startSet.Add(EarleyItem.Create(m_dfa.GetGoto(m_initialState, Symbol.Epsilon), 0));

            chart.Sets.Add(startSet);

            int i = 0;
            foreach (T token in symbols)
            {
                chart.Sets.Add(new Set<EarleyItem>());
                chart.Tokens.Add(token);

                ParseStep(chart, false, i);
                if (chart.Sets[i].Count == 0)
                {
                    break;
                }

                ++i;
            }

            ParseStep(chart, true, i);
            ++i;

            EarleyItem goalItem;
            Production goalProduction;
            if (!m_goal.TryGetGoal(chart.Sets[i - 1], out goalProduction, out goalItem))
            {
                ThrowParsingException(chart, i - 2);
            }
            return chart.BuildTree(evaluator, goalProduction, EarleySetItem.Create(goalItem, i - 1));
        }

        #endregion

        private void ThrowParsingException(EarleyChart<T, S> chart, int failedStateIndex)
        {
            // TODO: Get follow of completed productions
            Set<Symbol> expectedSymbols = new Set<Symbol>();
            if (failedStateIndex > 1)
            {
                foreach (LR0Item item in m_dfa.GetStateSet(failedStateIndex - 1))
                {
                    if (!item.IsComplete)
                    {
                        expectedSymbols.Add(item.DotSymbol);
                    }
                }
            }
            throw new ParsingException(chart.Tokens[failedStateIndex], expectedSymbols);
        }

        private void ParseStep(EarleyChart<T, S> chart, bool skipScan, int i)
        {
            WorkList<EarleyItem> workList = new WorkList<EarleyItem>(true);
            workList.Enqueue(chart.Sets[i]);

            EarleyItem item;
            while (workList.Dequeue(out item))
            {
                EarleySetItem setItem = EarleySetItem.Create(item, i);
                if (!skipScan)
                {
                    Scanner(chart, setItem);
                }

                if (item.Parent != i)
                {
                    Completer(chart, workList, setItem);
                }
            }
        }

        private void Scanner(EarleyChart<T, S> chart, EarleySetItem item)
        {
            int setIndex = item.SetIndex;

            int state = item.Item.State;
            int parent = item.Item.Parent;

            int k = m_dfa.GetGoto(state, chart.Tokens[setIndex].Symbol);
            if (k != EarleyDFA.InvalidState)
            {
                EarleySetItem newItem = chart.AddSetItem(setIndex + 1, k, parent);

                chart.AddLink(
                    newItem,
                    item,
                    EarleySetItem.None);

                int nk = m_dfa.GetGoto(k, Symbol.Epsilon);
                if (nk != EarleyDFA.InvalidState)
                {
                    chart.AddSetItem(setIndex + 1, nk, setIndex + 1);
                }
            }
        }

        private void Completer(EarleyChart<T, S> chart, WorkList<EarleyItem> workList, EarleySetItem item)
        {
            int setIndex = item.SetIndex;
            foreach (Production production in m_dfa.Completed(item.Item.State))
            {
                foreach (EarleySetItem pitem in chart.GetSetItems(item.Item.Parent))
                {
                    int pstate = pitem.Item.State;
                    int pparent = pitem.Item.Parent;

                    int k = m_dfa.GetGoto(pstate, production.LHS);
                    if (k != EarleyDFA.InvalidState)
                    {
                        EarleySetItem newItem = chart.AddSetItem(setIndex, k, pparent);
                        workList.Enqueue(newItem.Item);
                        chart.AddLink(
                            newItem,
                            pitem,
                            item);

                        int nk = m_dfa.GetGoto(k, Symbol.Epsilon);
                        if (nk != EarleyDFA.InvalidState)
                        {
                            newItem = chart.AddSetItem(setIndex, nk, setIndex);
                            workList.Enqueue(newItem.Item);
                        }
                    }
                }
            }
        }
    }
}